% Ejercicio "Ejercicios de gramáticas"
\subsection*{\fbox{\theejercicio} - Ejercicios de gram\'aticas}

Especificar si las siguientes gram\'aticas son LL(1) y por qu\'e:

\begin{center}
\begin{tabular}{|l|l|l|} \hline
                                     &                                      &                                             \\
{\em S} $\rightarrow$ {\em A}{\bf b} & {\em S} $\rightarrow$ {\em ABBA}     & {\em S} $\rightarrow$ {\bf a}{\em S}{\bf a} \\
{\em A} $\rightarrow$ {\bf a}        & {\em A} $\rightarrow$ {\bf a}        & {\em S} $\rightarrow$ {\bf b}{\em B}{\bf e} \\
{\em A} $\rightarrow$ {\em B}        & {\em A} $\rightarrow$ $\varepsilon$  & {\em B} $\rightarrow$ {\em C}               \\
{\em A} $\rightarrow$ $\varepsilon$  & {\em B} $\rightarrow$ {\bf b}        & {\em C} $\rightarrow$ {\bf c}{\em C}{\bf e} \\
{\em B} $\rightarrow$ {\bf b}        & {\em B} $\rightarrow$ $\varepsilon$  & {\em C} $\rightarrow$ {\bf d}               \\
{\em B} $\rightarrow$ $\varepsilon$  &                                      &                                             \\
                                     &                                      &                                             \\ \hline
\end{tabular}
\end{center}

% Solución del ejercicio
\subsubsection*{SOLUCI\'ON}

Gram\'atica 1)

\medskip

Puede observarse que la gram\'atica es ambigua porque reconoce el lexema \{{\tt b}\} mediante dos secuencias de derivaciones a izquierda distinstas:

$S \Rightarrow^1 Ab \Rightarrow^4 b$ \\
$S \Rightarrow^1 Ab \Rightarrow^3 Bb \Rightarrow^6 b$

y siendo ambigua nunca puede ser LL(1).

\medskip

Gram\'atica 2)

\medskip

Esta gram\'atica tambi\'en es ambigua y, por tanto, no LL(1). El lexema \{{\tt b}\} puede reconocerse con dos secuencias de derivaciones izquierdas distintas:

$S \Rightarrow^1 ABBA \Rightarrow^3 BBA \Rightarrow^4 bBA \Rightarrow^5 bA \Rightarrow^3 b$ \\
$S \Rightarrow^1 ABBA \Rightarrow^3 BBA \Rightarrow^5 BA \Rightarrow^4 bA \Rightarrow^3 b$

Algo similar sucede con el lexema \{{\tt a}\} tambi\'en reconocido por esta gram\'atica.

\medskip

Gram\'atica 3)

\medskip

Esta gram\'atica s\'{\i} es LL(1). Aunque la forma m\'as segura de afirmarlo consiste en construir su tabla LL(1) y constatar que no existen conflictos, puede conseguirse el mismo objetivo mediante un an\'alisis exhaustivo de la misma.

\smallskip

En primer lugar puede observarse que disponemos de tres no terminales \{{\em S, B, C}\} y que las reglas {\em S} se relacionan con las de {\em C} \'unicamente a trav\'es de un no terminal inerte {\em B} cuya \'unica regla es $B \rightarrow C$. Por tanto, a efectos anal\'{\i}ticos esta gram\'atica debe poseer los mismos conjuntos CABECERA y SIGUIENTE para \{{\em S, C}\} que la gram\'atica:

\begin{center}
\begin{tabular}{lcl}
{\em S} & $\rightarrow$ & {\bf a} {\em S} {\bf a} \\
{\em S} & $\rightarrow$ & {\bf b} {\em C} {\bf e} \\
{\em C} & $\rightarrow$ & {\bf c} {\em C} {\bf e} \\
{\em C} & $\rightarrow$ & {\bf d}                 \\
\end{tabular}
\end{center}

bastante m\'as f\'acil de analizar.

\smallskip

Primeramente debemos darnos cuenta de que las reglas 1 y 2 reconocen sin lugar a dudas un patr\'on de la forma $a^nbCea^n$ mientras que las reglas 3 y 4 reconocen $c^mde^m$. Este comportamiento es propio de las gram\'aticas de contexto libre, y la principal caracter\'{\i}stica que las diferencia de las gram\'aticas regulares, haci\'endolas reconocedoras de conjunto de lenguajes m\'as amplio.

\smallskip

A continuaci\'on, en nuestra gram\'atica reducida, vemos que un analizador LL(1) ir\'a aplicando la regla 1 mientras vaya encontr\'andose con tokens {\tt a}, hasta que llegue el momento en que se encuentre con el token {\tt b}. Se trata de una aproximaci\'on ante la que no cabe duda alguna puesto que ni {\tt a} ni {\tt b} forman parte de las reglas en que {\em C} es consecuente. Una vez encontrada dicha {\tt b} debe aplicarse forzosamente la regla 2 y, a partir de ella, las reglas asociadas a la {\em C}. Puede seguirse el mismo razonamiento para la secuencia de tokens que debe encontrarse a continuaci\'on: una secuencia de 0 o m\'as tokens {\tt c} seguida de una \'unica {\tt d}. Una vez llegados a este punto, la gram\'atica de contexto libre obliga a que, para reconocer el lexema como perteneciente a la gram\'atica, deba encontrarse una secuencia de tokens {\tt e} (en igual n\'umero que la secuencia de tokens {\tt c} previa), una {\tt e} adicional debida a la regla 2 y, finalmente una secuencia de tokens {\tt a} en igual n\'umero a la que se encontr\'o al principio del an\'alisis.

La tabla de an\'alisis LL(1) de esta gram\'atica ser\'{\i}a la siguiente:

\begin{center}
\begin{tabular}{|l|cccccc|} \hline
        & {\bf a} & {\bf b} & {\bf c} & {\bf d} & {\bf e} & {\bf \$} \\ \hline
{\em S} & 1       & 2       &         &         &         &          \\
{\em B} &         &         & 3       & 3       &         &          \\
{\em C} &         &         & 4       & 5       &         &          \\ \hline
\end{tabular}
\end{center}